//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 10⁴ 
// 0 <= height[i] <= 10⁵ 
// 
//
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 5180 👎 0


package LeetCode.editor.cn;

import java.util.Stack;

/**
 * @author ldltd
 * @date 2024-06-05 10:57:06
 * @description 42.接雨水
 */
public class TrappingRainWater{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 TrappingRainWater fun=new TrappingRainWater();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
 class Solution {
	/*一行一行的求 从左边开始，当t小于i时候+1,当t大于等于i时结算
    * 时间复杂度：如果最大的数是 mm，个数是 nn，那么就是 O(m*n)。
    空间复杂度：O(1)O。*/
	public int trap1(int[] height) {
		int res=0,t=0;
		boolean flag=false;
		//求最高层，方便确定遍历的次数
		int maxh=getMax(height);
		for (int i = 0; i <=maxh; i++) {
			//标记是否更新
			flag=false;
			t=0;
			for (int j = 0; j < height.length; j++) {
				if(flag&&height[j]<i){
					t++;
				}
				if(height[j]>=i){
					res+=t;
					t=0;
					flag=true;
				}
			}

		}
		return res;
	}
	private int getMax(int[] height){
		int res=0;
		for (int i = 0; i < height.length; i++) {
			if(height[i]>res) res=height[i];
		}
		return res;
	}
	/*一列一列的求，每次只考虑左右两边最高的墙，当前列的水就是其中最小的那一个剪当前列
    * 时间复杂度：O(n²），遍历每一列需要 n，找出左边最高和右边最高的墙加起来刚好又是一个 nn，所以是 n²。
    空间复杂度：O(1）*/
	public int trap2(int[] height) {
		int res=0,l=0,r=0;
		//最边的不考虑，一定没有，所以下标从1到length-2;
		for (int i = 1; i < height.length-1; i++) {
			l=0;
			for (int j = i-1; j >=0 ; j--) {
				if(height[j]>l) l=height[j];
			}
			r=0;
			for (int j = i+1;j< height.length-1 ; j++) {
				if(height[j]>r) r=height[j];
			}
			int min=Math.min(l,r);
			if(min>height[i]) res+=min-height[i];
		}
		return res;
	}
	/*
    * 动态规划，每次求最高最低的时候，
    * 对于 max_left我们其实可以这样求。
    l[i] = Max(l [i-1],height[i-1])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
    对于 r我们可以这样求。
    r[i] = Max(r[i+1],height[i+1]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
    * 时间复杂度：O(n)
    空间复杂度：O(n)，用来保存每一列左边最高的墙和右边最高的墙
*/
	public int trap3(int[] height) {
		int res=0;
		int h=height.length;
		int [] l=new int[h];
		int [] r=new int[h];
		//求每个点左边的最大
		for (int i = 0; i < h-1; i++) {
			l[i]=Math.max(l[i-1],height[i-1]);
		}
		//求每个点右边的最大
		for (int i = h-2; i >=0; i--) {
			r[i]=Math.max(r[i+1],height[i+1]);
		}
//            求值
		for (int i = 0; i < h-1; i++) {
			int min=Math.min(l[i],r[i]);
			if(min>height[i]) res+=min-height[i];
		}
		return  res;
	}

	/*双指针
    * 对空间复杂度进行进一步的优化。
    例如这道题中，可以看到，l [ i ] 和 r [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。
    所以我们可以不用数组，只用一个元素就行了。我们先改造下 l。
    * maxl = Math.max(maxl, height[i - 1]);
    * 而maxr是从右往左的，求值是从左往右，还不能去掉
    * 所以采用两个指针，依次更新左右两格的接水
    */
	public int trap4(int[] height) {
		int res=0,l=1,r=height.length-2,maxl=0,maxr=0;
		for (int i = 1; i < height.length-1; i++) {
			//从左往右
			if(height[l-1]<height[r+1]){
				maxl=Math.max(maxl,height[l-1]);
				int min=maxl;
				if(min>height[l]){
					res+=min-height[l];
				}
				l++;
				//从右往左
			}else{
				maxr=Math.max(maxr,height[r+1]);
				int min=maxr;
				if(min>height[r]){
					res+=min-height[r];
				}
				r--;
			}
		}
		/*第二种写法*/
       /*     while(l<r){
                maxl=Math.max(maxl,height[l]);
                maxr=Math.max(maxr,height[r]);
                if(height[l]<height[r]){
                    res+=maxl-height[l];
                    l++;
                }else {
                    res+=maxr-height[r];
                    r--;
                }
            }*/
		return res;
	}
	/*单调栈
    * 总体的原则就是，
1当前高度小于等于栈顶高度，入栈，指针后移。
2当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，
* 重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
* 时间复杂度：虽然 while 循环里套了一个 while 循环，但是考虑到每个元素最多访问两次，入栈一次和出栈一次，所以时间复杂度是 O(n)。
空间复杂度：O(n)。栈的空间。
*/
	public int trap5(int[] height) {
		int res=0;
		Stack<Integer> stack = new Stack<>();
		int current=0;
		while (current<height.length){
			//如果栈不为空且当前的高度大于栈顶高度就一直拿出
			while(!stack.empty()&&height[current]>height[stack.peek()]){
				//出栈
				int pop = stack.pop();
				//栈空结束
				if(stack.isEmpty()) break;
				int l = stack.peek();
				//两墙距离
				int currWidth=current-l-1;
				//高度
				int currHeight = Math.min(height[l], height[current])-height[pop];
				res+=currWidth*currHeight;
			}
			//否则把当前指向的墙入栈，且指针后移
			stack.push(current++);
		}
		return res;
	}
}

//leetcode submit region end(Prohibit modification and deletion)
}

